home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Python 1.3.3 / stdwin / Tools / oldglob.c < prev    next >
Text File  |  1995-12-21  |  9KB  |  544 lines
  1. /* This software is copyright (c) 1986 by Stichting Mathematisch Centrum.
  2.  * You may use, modify and copy it, provided this notice is present in all
  3.  * copies, modified or unmodified, and provided you don't make money for it.
  4.  *
  5.  * Written 86-jun-28 by Guido van Rossum, CWI, Amsterdam <guido@mcvax.uucp>
  6.  */
  7.  
  8. /*
  9.  * 'Glob' routine -- match *, ? and [...] in filenames.
  10.  * Extra services: initial ~username is replaced by username's home dir,
  11.  * initial ~ is replaced by $HOME, initial $var is replaced by
  12.  * return value of getenv("var").
  13.  * Quoting convention: \ followed by a magic character inhibits its
  14.  * special meaning.
  15.  * Nonexisting $var is treated as empty string; nonexisting ~user
  16.  * is copied literally.
  17.  */
  18.  
  19. #include <stdio.h>
  20. #include <strings.h>
  21. #include <ctype.h>
  22. #include <pwd.h>
  23. #include <sys/types.h>
  24. #include <sys/dir.h>
  25.  
  26. struct passwd *getpwnam();
  27. char *getenv();
  28. char *malloc();
  29. char *realloc();
  30.  
  31. #define EOS '\0'
  32. #define SEP '/'
  33. #define DOT '.'
  34. #define QUOTE '\\'
  35.  
  36. #define BOOL int
  37. #define NO 0
  38. #define YES 1
  39.  
  40. #define MAXPATH 1024
  41. #define MAXBASE 256
  42.  
  43. #define META(c) ((char)((c)|0200))
  44. #define M_ALL META('*')
  45. #define M_ONE META('?')
  46. #define M_SET META('[')
  47. #define M_RNG META('-')
  48. #define M_END META(']')
  49.  
  50. struct flist {
  51.     int len;
  52.     char **item;
  53. };
  54.  
  55. /* Make a null-terminated string of the chars between two pointers */
  56. /* (Limited length, static buffer returned) */
  57.  
  58. static char *
  59. makestr(start, end)
  60.     char *start;
  61.     char *end;
  62. {
  63.     static char buf[100];
  64.     char *p= buf;
  65.     
  66.     while (start < end && p < &buf[100])
  67.         *p++ = *start++;
  68.     *p= EOS;
  69.     return buf;
  70. }
  71.  
  72. /* Append string to buffer, return new end of buffer.  Guarded. */
  73.  
  74. static char *
  75. addstr(dest, src, end)
  76.     char *dest;
  77.     char *src;
  78.     char *end;
  79. {
  80.     while (*dest++ = *src++) {
  81.         if (dest >= end)
  82.             break;
  83.     }
  84.     return --dest;
  85. }
  86.  
  87. /* Form a pathname by concatenating head, maybe a / and tail. */
  88. /* Truncates to space available. */
  89.  
  90. static void
  91. formpath(dest, head, tail, size)
  92.     char *dest;
  93.     char *head;
  94.     char *tail;
  95.     unsigned int size; /* sizeof dest */
  96. {
  97.     char *start= dest;
  98.     
  99.     for (;;) {
  100.         if (--size == 0)
  101.             goto out;
  102.         if ((*dest++ = *head++) == EOS)
  103.             break;
  104.     }
  105.     if (*tail != EOS && size != 0) {
  106.         --dest;
  107.         ++size;
  108.         if (dest > start && dest[-1] != SEP) {
  109.             *dest++ = SEP;
  110.             --size;
  111.         }
  112.         for (;;) {
  113.             if (--size == 0)
  114.                 goto out;
  115.             if ((*dest++ = *tail++) == EOS)
  116.                 break;
  117.         }
  118.     }
  119.     return;
  120.     
  121.  out:    *dest= EOS;
  122. }
  123.  
  124. /* Find a user's home directory, NULL if not found */
  125.  
  126. static char *
  127. gethome(username)
  128.     char *username;
  129. {
  130.     struct passwd *p;
  131.     
  132.     p= getpwnam(username);
  133.     if (p == NULL)
  134.         return NULL;
  135.     return p->pw_dir;
  136. }
  137.  
  138. /* String compare for qsort */
  139.  
  140. static int
  141. compare(p, q)
  142.     char **p;
  143.     char **q;
  144. {
  145.     return strcmp(*p, *q);
  146. }
  147.  
  148. /*
  149.  * Maintain lists of strings.
  150.  * When memory is full, data is lost but 
  151.  */
  152.  
  153. static void
  154. addfile(list, head, tail)
  155.     struct flist *list;
  156.     char *head;
  157.     char *tail;
  158. {
  159.     char *str;
  160.     
  161.     str= malloc((unsigned) strlen(head) + strlen(tail) + 2);
  162.     
  163.     if (str == NULL)
  164.         return;
  165.     if (list->item == 0) {
  166.         list->len= 0;
  167.         list->item= (char**) malloc(sizeof(char*));
  168.     }
  169.     else {
  170.         list->item= (char**) realloc((char*)list->item,
  171.                 (unsigned) (list->len+1)*sizeof(char*));
  172.         if (list->item == 0)
  173.             list->len= 0;
  174.     }
  175.     if (list->item != NULL) {
  176.         formpath(str, head, tail, MAXPATH);
  177.         list->item[list->len++]= str;
  178.     }
  179.     else
  180.         free(str);
  181. }
  182.  
  183. /* Clear the fields of a struct flist before first use */
  184.  
  185. static void
  186. clear(list)
  187.     struct flist *list;
  188. {
  189.     list->len= 0;
  190.     list->item= NULL;
  191. }
  192.  
  193. /* Free memory held by struct flist after use */
  194.  
  195. static void
  196. discard(list)
  197.     struct flist *list;
  198. {
  199.     int i= list->len;
  200.     
  201.     if (list->item != NULL) {
  202.         while (--i >= 0) {
  203.             if (list->item[i] != NULL)
  204.                 free(list->item[i]);
  205.         }
  206.         free((char*)list->item);
  207.         list->item= NULL;
  208.     }
  209.     list->len= 0;
  210. }
  211.  
  212. /* Pattern matching function for filenames */
  213. /* Each occurrence of the * pattern causes a recursion level */
  214.  
  215. static BOOL
  216. match(name, pat)
  217.     char *name;
  218.     char *pat;
  219. {
  220.     char c, k;
  221.     BOOL ok;
  222.     
  223.     while ((c= *pat++) != EOS) {
  224.         switch (c) {
  225.  
  226.         case M_ONE:
  227.             if (*name++ == EOS)
  228.                 return NO;
  229.             break;
  230.  
  231.         case M_ALL:
  232.             if (*pat == EOS)
  233.                 return YES;
  234.             for (; *name != EOS; ++name) {
  235.                 if (match(name, pat))
  236.                     return YES;
  237.             }
  238.             return NO;
  239.  
  240.         case M_SET:
  241.             ok= NO;
  242.             k= *name++;
  243.             while ((c= *pat++) != M_END) {
  244.                 if (*pat == M_RNG) {
  245.                     if (c <= k && k <= pat[1])
  246.                         ok= YES;
  247.                     pat += 2;
  248.                 }
  249.                 else if (c == k)
  250.                     ok= YES;
  251.             }
  252.             if (!ok)
  253.                 return NO;
  254.             break;
  255.  
  256.         default:
  257.             if (*name++ != c)
  258.                 return NO;
  259.             break;
  260.  
  261.         }
  262.     }
  263.     return *name == EOS;
  264. }
  265.  
  266. /* Perform pattern matching for one segment of the pathname */
  267.  
  268. static void
  269. segment(files, mid, pat)
  270.     struct flist *files;
  271.     char *mid;
  272.     char *pat;
  273. {
  274.     char path[MAXPATH];
  275.     int i;
  276.     DIR *dirp;
  277.     struct direct *dp;
  278.     struct flist new;
  279.     
  280.     clear(&new);
  281.     for (i= 0; i < files->len; ++i) {
  282.         strcpy(path, files->item[i]);
  283.         strcat(path, mid);
  284.         free(files->item[i]);
  285.         files->item[i]= NULL;
  286.         dirp= opendir(path);
  287.         if (dirp == NULL)
  288.             continue;
  289.         while ((dp= readdir(dirp)) != NULL) {
  290.             if (*dp->d_name == DOT && *pat != DOT)
  291.                 ; /* No meta-match on initial '.' */
  292.             else if (match(dp->d_name, pat))
  293.                 addfile(&new, path, dp->d_name);
  294.         }
  295.         closedir(dirp);
  296.     }
  297.     discard(files);
  298.     *files= new;
  299. }
  300.  
  301. /* Finish by matching the rest of the pattern (which has no metas) */
  302.  
  303. static void
  304. findfiles(files, tail)
  305.     struct flist *files;
  306.     char *tail;
  307. {
  308.     int i;
  309.     struct flist new;
  310.     char path[MAXPATH];
  311.  
  312.     if (*tail == EOS || files->len == 0)
  313.         return;
  314.     clear(&new);
  315.     for (i= 0; i < files->len; ++i) {
  316.         strcpy(path, files->item[i]);
  317.         strcat(path, tail);
  318.         free(files->item[i]);
  319.         files->item[i]= NULL;
  320.         if (access(path, 0) == 0)
  321.             addfile(&new, path, "");
  322.     }
  323.     discard(files);
  324.     *files= new;
  325. }
  326.  
  327. static void
  328. glob1(pat, files)
  329.     char *pat;
  330.     struct flist *files;
  331. {
  332.     char mid[MAXPATH];
  333.     char *end= mid;
  334.     char *basestart= mid;
  335.     BOOL meta= NO;
  336.     char c;
  337.     
  338.     clear(files);
  339.     addfile(files, "", "");
  340.     for (;;) {
  341.         switch (c= *pat++) {
  342.  
  343.         case EOS:
  344.         case SEP:
  345.             *end= EOS;
  346.             if (meta) {
  347.                 if (basestart == mid)
  348.                     segment(files, "", basestart);
  349.                 else if (basestart == mid+1) {
  350.                     static char sepstr[]= {SEP, EOS};
  351.                     segment(files, sepstr, basestart);
  352.                 }
  353.                 else {
  354.                     basestart[-1]= EOS;
  355.                     segment(files, mid, basestart);
  356.                 }
  357.                 if (files->len == 0)
  358.                     return;
  359.                 end= basestart= mid;
  360.                 meta= NO;
  361.             }
  362.             else if (c == EOS)
  363.                 findfiles(files, mid);
  364.             if (c == EOS)
  365.                 return;
  366.             *end++= c;
  367.             basestart= end;
  368.             break;
  369.  
  370.         case M_ALL:
  371.         case M_ONE:
  372.         case M_SET:
  373.             meta= YES;
  374.             /* Fall through */
  375.         default:
  376.             *end++ = c;
  377.  
  378.         }
  379.     }
  380. }
  381.  
  382. /*
  383.  * The main 'glob' routine: does $ and ~ substitution and \ quoting,
  384.  * and then calls 'glob1' to do the pattern matching.
  385.  * Returns 0 if file not found, number of matches otherwise.
  386.  * The matches found are appended to the buffer, separated by
  387.  * EOS characters.  If no matches were found, the pattern is copied
  388.  * to the buffer after $ and ~ substitution and \ quoting.
  389.  */
  390.  
  391. int
  392. glob(pat, buf, size)
  393.     char *pat;
  394.     char *buf;
  395.     unsigned int size; /* sizeof buf */
  396. {
  397.     char *p, *q;
  398.     char c;
  399.     struct flist files;
  400.     char *start= buf;
  401.     char *end= buf+size;
  402.     
  403.     c= *pat;
  404.     if (c == '~') {
  405.         p= ++pat;
  406.         while (*p != EOS && *p != SEP)
  407.             ++p;
  408.         if (p == pat) {
  409.             q= getenv("HOME");
  410.             if (q == NULL)
  411.                 --pat;
  412.             else
  413.                 buf= addstr(buf, q, end);
  414.         }
  415.         else {
  416.             q= gethome(makestr(pat, p));
  417.             if (q == NULL)
  418.                 --pat;
  419.             else {
  420.                 buf= addstr(buf, q, end);
  421.                 pat= p;
  422.             }
  423.         }
  424.     }
  425.     else if (c == '$') {
  426.         p= ++pat;
  427.         while (isalnum(*p) || *p == '_')
  428.             ++p;
  429.         q= getenv(makestr(pat, p));
  430.         if (q != NULL)
  431.             buf= addstr(buf, q, end);
  432.         pat= p;
  433.     }
  434.     else if (c == QUOTE && (pat[1] == '$' || pat[1] == '~'))
  435.         ++pat;
  436.     
  437.     while (buf < end && (c= *pat++) != EOS) {
  438.         switch (c) {
  439.         
  440.         case QUOTE:
  441.             if ((c= *pat++) != EOS && index("\\*?[", c) != NULL)
  442.                 *buf++ = c;
  443.             else {
  444.                 *buf++ = QUOTE;
  445.                 --pat;
  446.             }
  447.             break;
  448.         
  449.         case '*':
  450.             *buf++ = M_ALL;
  451.             break;
  452.         
  453.         case '?':
  454.             *buf++ = M_ONE;
  455.             break;
  456.         
  457.         case '[':
  458.             if (*pat == EOS || index(pat+1, ']') == NULL) {
  459.                 *buf++ = c;
  460.                 break;
  461.             }
  462.             *buf++ = M_SET;
  463.             c= *pat++;
  464.             do {
  465.                 *buf++ = c;
  466.                 if (*pat == '-' && (c= pat[1]) != ']') {
  467.                     *buf++ = M_RNG;
  468.                     *buf++= c;
  469.                     pat += 2;
  470.                 }
  471.             } while ((c= *pat++) != ']');
  472.             *buf++ = M_END;
  473.             break;
  474.         
  475.         default:
  476.             *buf++ = c;
  477.             break;
  478.  
  479.         }
  480.     }
  481.     *buf= EOS;
  482.     
  483.     glob1(start, &files);
  484.     
  485.     if (files.len == 0) {
  486.         /* Change meta characters back to printing characters */
  487.         for (buf= start; *buf != EOS; ++buf) {
  488.             if (*buf & 0200)
  489.                 *buf &= ~0200;
  490.         }
  491.         return 0; /* No match */
  492.     }
  493.     else {
  494.         int i, len;
  495.         
  496.         qsort((char*)files.item, files.len, sizeof(char*), compare);
  497.         buf= start;
  498.         *buf= EOS;
  499.         for (i= 0; i < files.len; ++i) {
  500.             len= strlen(files.item[i]);
  501.             if (len+1 > size)
  502.                 break;
  503.             strcpy(buf, files.item[i]);
  504.             buf += len+1;
  505.             size -= len+1;
  506.         }
  507.         discard(&files);
  508.         return i;
  509.     }
  510. }
  511.  
  512. #ifdef MAIN
  513. /*
  514.  * Main program to test 'glob' routine.
  515.  */
  516.  
  517. main(argc, argv)
  518.     int argc;
  519.     char **argv;
  520. {
  521.     int i, j, n;
  522.     char *p;
  523.     char buffer[10000];
  524.  
  525.     if (argc < 2) {
  526.         fprintf(stderr, "usage: %s pattern ...\n", argv[0]);
  527.         exit(2);
  528.     }
  529.     for (i= 1; i < argc; ++i) {
  530.         printf("%s: ", argv[i]);
  531.         n= glob(argv[i], buffer, sizeof buffer);
  532.         printf("%d\n", n);
  533.         p= buffer;
  534.         if (n == 0)
  535.             ++n;
  536.         for (j= 0; j < n; ++j) {
  537.             printf("\t%s\n", p);
  538.             p += strlen(p) + 1;
  539.         }
  540.     }
  541.     exit(0);
  542. }
  543. #endif
  544.